/**
 * 选择排序
 * 		第一次从下标为0的开始下标为0的这个数与后面的n-1个进行比较；找出最小或者最大的放在下标为0的这个位置；
 * 		第二次从下标为1的开始比较；查询剩下的最大或者最小值；放在下标为1的位置；以此类推；直到排序完成
 * 
 * 冒泡排序
 * 		依次比较相邻的两个数，将小数放在前面，大数放在后面。
 * 		即在第一趟：首先比较第1个和第2个数，将小数放前，大数      放后。然后比较第2
 * 		个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。
 * 		在第二趟：仍从第一对数开始比较
 * 		（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个 数），将小数放前中，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟
 * 		结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。
 * 		这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
 * 
 * 
 * 插入排序
 * 		有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,
 * 		插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。
 * 		是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），
 * 		而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
 * 		插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
 * 
 * 
 * 二分查找（二分查找又称折半查找）
 * 二分排序（二分排序就是折半插入排序）
 * 		二分排序是指利用二分法的思想对插入排序进行改进的一种插入排序算法，不同于二叉排序，可以利用数组的特点快速定位指定索引的元素。
 * 		用自己的话总结就是，从第二位开始，使用二分查找找到这个数在左侧有序数组中的下标，将下标右侧的元素右移一位，将这个数插入到下标中
 * 
 * 希尔排序
 * 		希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。
 * 		希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
 * 		希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。 
 * 
 * 
 * 归并排序
 * 		归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
 * 		将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
 * 
 * 
 * 快速排序
 * 		(参考百度百科) 
 * 		速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
 * 		然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 * 
 * 		设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，
 * 		所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，
 * 		也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
 * 		一趟快速排序的算法是：
 * 		1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
 * 		2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
 * 		3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
 * 		4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
 * 		5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，
 * 		直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
 * 		通过递归达到多趟的目的
 * 
 * 
 * 
 **********************************************************************
 * 外排序
 * 
 * 大数据多路归并排序
 * https://blog.csdn.net/wongson/article/details/49209903
 * 
 * 多路归并
 * https://blog.csdn.net/u010367506/article/details/23565421
 * 
 * 常见的内排序和外排序算法
 * https://www.epubit.com/selfpublish/article/333;jsessionid=4D120BF407C6047A794DD322A181CC8F
 * 
 * 
 * 算法问题分类---Top-K问题与多路归并排序
 * https://blog.csdn.net/hishentan/article/details/39099923
 * 
 * 败者树
 * https://www.cnblogs.com/iyjhabc/p/3141665.html
 * 
 * 胜者树与败者树
 * https://blog.csdn.net/wypblog/article/details/8074831
 * 
 */
package algorithm.sort;